#include <stdio.h>

#define size 100
typedef int ElemType;

//三元组
typedef struct{
    //矩阵的横纵坐标
    int i, j;
    //该位置的值
    int v;
}Triple;

//压缩矩阵
typedef struct{
    Triple data[size];
    int m;
    int n;
    int nonzeroCount;
}Matrix;
/**
 * @brief 打印矩阵
 * 
 * @param matrix 压缩矩阵
 */
void print(Matrix matrix){
    int p = 0;
    for(int i = 0; i < matrix.m; i++){
        for(int j = 0; j < matrix.n; j++){
            if(p < matrix.nonzeroCount && matrix.data[p].i == i && matrix.data[p].j == j){
                printf("%d\t", matrix.data[p++]);
            }else{
                printf("%d\t", 0);
            }
        }
        printf("\n");
    }
}
/**
 * @brief 矩阵的转置 O(n * m * n)
 * 
 * @param A 原矩阵的压缩矩阵
 * @param B 转置后的原矩阵的压缩矩阵
 */
void transpose(Matrix A, Matrix &B){
    B.m = A.n;
    B.n = A.m;
    B.nonzeroCount = A.nonzeroCount;
    //从列数为0的依次开始找
    int cur = 0;
    for(int col = 0; col < A.n; col++){
        for(int p = 0; p < A.nonzeroCount; p++){
            if(A.data[p].j == col){
                B.data[cur] = A.data[p];
                B.data[cur].i = A.data[p].j;
                B.data[cur].j = A.data[p].i;
                cur++;
            }
        }
    }
}

/**
 * @brief 快速转置O(2*m*n + n)
 * 
 * @param A 原矩阵的压缩矩阵
 * @param B 转置后的原矩阵的压缩矩阵
 */
void fastTranspose(Matrix A, Matrix &B){
    B.m = A.n;
    B.n = A.m;
    B.nonzeroCount = A.nonzeroCount;

    //统计原矩阵每列非零元的个数
    int num[100] = {0};
    for(int i = 0; i < A.nonzeroCount; i++){
        num[A.data[i].j]++;
    }
    //存储每列第一个非零元素在B中存储的位置
    int pos[100] = {0};
    for(int j = 0; j < A.n; j++){
        pos[j] = pos[j - 1] + num[j - 1];
    }
    
    for(int i = 0; i < A.nonzeroCount; i++){
        Triple triple = A.data[i];
        int index = pos[triple.j];

        B.data[index].i = triple.j;
        B.data[index].j = triple.i;
        B.data[index].v = triple.v;

        //下一次该列元素在B中的位置需加1
        pos[triple.j]++;

    }
}


